TNotes.leetcode

Appearance

⏰0963. 最小面积矩形 II【中等】

0963. 最小面积矩形 II【中等】 ​

1. 📝 题目描述 ​

给你一个 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。

返回由这些点形成的任意矩形的最小面积，矩形的边 不一定 平行于 X 轴和 Y 轴。如果不存在这样的矩形，则返回 0。

答案只需在10^-5 的误差范围内即可被视作正确答案。

示例 1：

img

txt
输入：points = [[1,2],[2,1],[1,0],[0,1]]
输出：2.00000

解释：
最小面积矩形由 [1,2]、[2,1]、[1,0]、[0,1] 组成，其面积为 2。

示例 2：

img

txt
输入：points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
输出：1.00000

解释：
最小面积矩形由 [1,0]、[1,1]、[2,1]、[2,0] 组成，其面积为 1。

示例 3：

img

txt
输入：points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
输出：0

解释：
无法由这些点组成任何矩形。

提示：

  • 1 <= points.length <= 50
  • points[i].length == 2
  • 0 <= xi, yi <= 4 * 10^4
  • 所有给定的点都是唯一的。

2. 🎯 s.1 - 哈希表 ​

js
/**
 * @param {number[][]} points
 * @return {number}
 */
var minAreaFreeRect = function (points) {
  const n = points.length
  if (n < 4) return 0

  // 用哈希表存储每条对角线的中点和长度
  const map = new Map()

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const [x1, y1] = points[i]
      const [x2, y2] = points[j]

      // 对角线中点（用2倍坐标避免浮点数）
      const cx = x1 + x2
      const cy = y1 + y2
      // 对角线长度的平方
      const dist = (x1 - x2) ** 2 + (y1 - y2) ** 2

      const key = `${cx},${cy},${dist}`
      if (!map.has(key)) map.set(key, [])
      map.get(key).push([i, j])
    }
  }

  let minArea = Infinity

  // 检查每组共享中点和对角线长度的点对
  for (const pairs of map.values()) {
    if (pairs.length < 2) continue

    for (let i = 0; i < pairs.length; i++) {
      for (let j = i + 1; j < pairs.length; j++) {
        const [p1, p2] = pairs[i] // 对角线1的两端点索引
        const [p3, p4] = pairs[j] // 对角线2的两端点索引

        const [x1, y1] = points[p1]
        const [x3, y3] = points[p3]
        const [x4, y4] = points[p4]

        // 从 p1 出发到 p3 和 p4 的两条边
        const v1x = x3 - x1,
          v1y = y3 - y1
        const v2x = x4 - x1,
          v2y = y4 - y1

        // 检查是否垂直（向量点积为0）
        if (v1x * v2x + v1y * v2y === 0) {
          const len1 = Math.sqrt(v1x ** 2 + v1y ** 2)
          const len2 = Math.sqrt(v2x ** 2 + v2y ** 2)
          minArea = Math.min(minArea, len1 * len2)
        }
      }
    }
  }

  return minArea === Infinity ? 0 : minArea
}
  • 时间复杂度：O(n2)，枚举所有点对，哈希表查找和比较都是常数时间
  • 空间复杂度：O(n2)，哈希表最多存储 O(n2) 个点对

算法思路：

  • 矩形性质：对角线互相平分且长度相等
  • 枚举对角线：遍历所有点对作为潜在对角线，计算中点和长度，用字符串 "cx,cy,dist" 作为键存入哈希表
  • 查找矩形：对于中点和对角线长度相同的两条对角线，检查它们是否垂直（向量点积为 0）
  • 计算面积：若垂直则构成矩形，计算两条边长（对角线的一半）的乘积
  • 返回最小面积，若不存在矩形返回 0